从小白开始刷算法 bfs篇 leetcode.102

虽然算法很难，但不应该就放弃。这是一个学习笔记，希望你们喜欢~

先自己尝试写，大概十几分钟仍然写不出来 看思路，再尝试跟着思路写 仍然写不出来，再看视频 b站up视频推荐：爱学习的饲养员

leetcode其他文章：

数组篇： 从小白开始刷算法 数组篇 leetcode.485 从小白开始刷算法 数组篇 leetcode.283 从小白开始刷算法 数组篇 leetcode.27

链表篇： 从小白开始刷算法 ListNode 链表篇 leetcode.203 从小白开始刷算法 ListNode 链表篇 leetcode.206

队列篇 从小白开始刷算法 ListNode 链表篇 leetcode.933

栈篇 从小白开始刷算法 Stack 栈篇 leetcode.20 从小白开始刷算法 Stack 栈篇 leetcode.496

哈希篇 从小白开始刷算法 Hash 哈希篇 leetcode.217 从小白开始刷算法 Hash 哈希篇 leetcode.705

树篇 从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144 从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94 从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94

堆篇 从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215 小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692

双指针篇

从小白开始刷算法 对撞双指针 leetcode.881 从小白开始刷算法 快慢双指针篇 leetcode.141

二分法篇 从小白开始刷算法 二分法篇 leetcode.704 从小白开始刷算法 二分法篇 leetcode.35 从小白开始刷算法 二分法篇 leetcode.162 从小白开始刷算法 二分法篇 leetcode.74

滑动窗口篇 从小白开始刷算法 滑动窗口篇 leetcode.209 从小白开始刷算法 滑动窗口篇 leetcode.1456

递归篇 从小白开始刷算法 递归篇 leetcode.509 从小白开始刷算法 递归篇 leetcode.206

分治法篇 从小白开始刷算法 分治法篇 leetcode.169 从小白开始刷算法 分治法篇 leetcode.53

回溯法篇 从小白开始刷算法 回溯法篇 leetcode.22 从小白开始刷算法 回溯法篇 leetcode.78

dfs篇 从小白开始刷算法 dfs篇 leetcode.938 从小白开始刷算法 dfs篇 leetcode.200

bfs篇

难度：中等

题目：

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]] 示例 2：

输入：root = [1] 输出：[[1]] 示例 3：

输入：root = [] 输出：[]

题目来源：力扣（LeetCode）

BFS（广度优先搜索）是一种图遍历算法，用于在一个图或树的数据结构中从给定的起始节点开始，逐层地向外探索并访问其邻居节点。

BFS 的基本思想是通过维护一个队列来实现。起始时将起始节点放入队列中，然后从队列中取出一个节点，访问该节点，并将其未访问过的邻居节点放入队列中。然后继续从队列中取出节点，重复上述操作，直到队列为空。

BFS 的过程可以用以下步骤概括：

BFS 通常用于解决以下问题：

搜索最短路径：BFS 在图中搜索最短路径的能力使其非常适用于寻找两个节点之间的最短路径。

遍历或搜索树或图：BFS 可以用于遍历或搜索树或图的所有节点，确保每个节点都被访问到。

连通性检测：BFS 可以用于检测图或树中的连通性，即确定是否存在从一个节点到另一个节点的路径。

能否写出：能写出。

时间：15分钟多 比dfs好理解

思路：

主要是进入循环，直到队列q为空：

通过队列实现了层次遍历，利用队列的先入先出特性，保证了按层遍历节点，并且按层存储节点值。

时间复杂度：O(N) 其中

空间复杂度：O(N)

dfs：